// 统计一个数字在排序数组中出现的次数。
// 示例 1:
// 输入: nums = [5,7,7,8,8,10], target = 8
// 输出: 2
// 示例 2:

// 输入: nums = [5,7,7,8,8,10], target = 6
// 输出: 0

// 限制：
// 0 <= 数组长度 <= 50000

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

// ①循环
var search = function(nums, target) {
    let count = 0, len = nums.length;
    for(let i=0;i<=len;i++) {
        if(nums[i] === target) {
            count++;
        }
    }
    return count;
};

console.log(search([5], 5));

// ② 双指针法

// ③ 二分法1，找到当前数组中target的左边界，右边界，计算右边界-左边界
var search = function(nums, target) {
    let length = nums.length,
        start = -1,
        end = -1;
    
    let left = 0,
        right = length-1;
    
    // 找左边界
    while(left <= right) {
        let mid = Math.floor((left + right)/2);
        if(nums[mid] === target) {
            start = mid;
            right = mid - 1;
        }else if(nums[mid] > target) {
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    
    left = 0,
    right = length-1;
    
    // 找右边界
    while(left <= right) {
        let mid = Math.floor((left + right)/2);
        if(nums[mid] === target) {
            end = mid;
            left = mid + 1;
        }else if(nums[mid] > target) {
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    
    // start === -1说明没找到这个数,return 0
    return start === -1 ? 0 : (end - start + 1);
};

console.log(search([5], 5));

// ④二分法2，找到当前这个数的起始索引，然后从当前索引往后计数
var search = function(nums, target) {
    let count = 0,
        left = 0,
        right = nums.length - 1;
    
    let start = -1;
    while(left <= right) {
        let mid = (left + right) >> 1;
        if(nums[mid] === target) {
            // mid值等于target值
            start = mid;
            right = mid-1;
        }else if(nums[mid] > target) {
            // mid值>target值
            right = mid-1;
        }else {
            left = mid+1;
        }
    }
    
    right = nums.length - 1;
    while(start <= right) {
        if(nums[start] === target){
            count++;
            start++;
        }else {
            return count;
        };
    }
    
    return count;
};

console.log(search([0, 1, 4, 5, 5], 5));